class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n+10);
        if(s[0]!='0')
            dp[0]++;
        else
            return 0;

        if(n==1)
            return dp[0];

        int t=((s[0]-'0')*10+s[1]-'0');

        if(s[1]!='0')
        {
            dp[1]++;
            
            if(t>=10&&t<=26)
            {
                dp[1]++;
            }
        }
        else
        {
            if(t>=10&&t<=26)
            {
                dp[1]++;
            }
            else
            {
                return 0;
            }
        }
        for(int i=2;i<n;++i)
        {
            if(s[i]!='0')
            {
                dp[i]+=dp[i-1];
            }
            int x=((s[i-1]-'0')*10+s[i]-'0');
            if(x>=10&&x<=26)
            {
                dp[i]+=dp[i-2];
            }
        }
        return dp[n-1];
    }
};
